DP with cumulative sum
dynamic programming while cumulative sum.
ABC179D
Dynamic generation of cumulative sums during DP, etc.
ABC179D
code:python
def accum_generation(N):
"""
>> accum_generation(10)
1, 0, 1, 1, 1, 2, 2, 3, 4, 5
"""
value = 0 * (N + 10)
accum = 0 * (N + 10)
value0 = 1
accum0 = 1
for pos in range(1, N):
ret = (accumpos - 2 - accumpos - 4)
valuepos = ret
accumpos = accumpos - 1 + ret
return value:N
---
This page is auto-translated from /nishio/累積和しながらDP. If you looks something interesting but the auto-translated English is not good enough to understand it, feel free to let me know at @nishio_en. I'm very happy to spread my thought to non-Japanese readers.